package com.yangli.leecode.mashib;

/**
 * @Description
 * @Author liyang
 * @Date 2023/1/13 13:10
 */
public class DynamicProgramming {
    public static void main(String[] args){
        DynamicProgramming dynamicProgramming = new DynamicProgramming();
/*        System.out.println(dynamicProgramming.walk(7, 2, 5, 3));//9
        System.out.println(dynamicProgramming.walkCache(7, 2, 5, 3));
        System.out.println(dynamicProgramming.walkDynamicProgramming(7, 2, 5, 3));*/

        System.out.println(dynamicProgramming.moneyTarget1(new int[]{1, 7, 3}, 10));
        System.out.println(dynamicProgramming.moneyTarget2(new int[]{1, 7, 3}, 10));
        System.out.println(dynamicProgramming.moneyTarget3(new int[]{1, 7, 3}, 10));
        System.out.println(dynamicProgramming.moneyTarget4(new int[]{1, 7, 3}, 10));

    }

    //暴力递归
    public int moneyTarget1(int[] arr, int target){
        if (arr == null || arr.length == 0 || target < 0) {
            return 0;
        }
        return moneyTargetProcess1(arr, 0, target);
    }

    private int moneyTargetProcess1(int[] arr, int index, int rest){
        if (index == arr.length) {//到边界位置，剩余0元表示，凑齐目标了
            return rest == 0 ? 1 : 0;
        }
/*        if (arr[index] == 0) {//这个属于细节优化
            return moneyTargetProcess1(arr, index + 1,rest);
        }*/
        int res = 0;
        for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
            res += moneyTargetProcess1(arr, index + 1, rest - (zhang * arr[index]));
        }
        return res;
    }

    //记忆搜索法==>缓存部分计算过程==>是一种以空间换时间的思路
    public int moneyTarget2(int[] arr, int target){
        if (arr == null || arr.length == 0 || target < 0) {
            return 0;
        }
        //HashMap<String,Integer> hashMap = new HashMap<>();//f(index,rest)==>有个好处，只会冗余需要的"index_rest"组合，而数组的方式需要申请全额的空间。例如[1000,2000] 100万 rest的空间不会出现1...999这样的情况
        int[][] dp = new int[arr.length + 1][target + 1];//缓存f(index,rest) [1,2,6]==f(2,4)有两种情况，无需重复计算的==>记忆搜索法==>减少部分计算过程
        for (int i = 0; i < arr.length + 1; i++) {
            for (int j = 0; j < target + 1; j++) {
                dp[i][j] = -1;//表示未计算过
            }
        }
        return moneyTargetProcess2(arr, 0, target, dp);
    }

    private int moneyTargetProcess2(int[] arr, int index, int rest, int[][] dp){
        if (dp[index][rest] != -1) {//获取到重复记录
            return dp[index][rest];
        }
        if (index == arr.length) {//到边界位置，剩余0元表示，凑齐目标了
            dp[index][rest] = rest == 0 ? 1 : 0;
            return dp[index][rest];
        }
/*        if (arr[index] == 0) {//这个属于细节优化
            return moneyTargetProcess1(arr, index + 1,rest);
        }*/
        int res = 0;
        for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
            res += moneyTargetProcess2(arr, index + 1, rest - (zhang * arr[index]), dp);
        }
        dp[index][rest] = res;
        return dp[index][rest];
    }

    //简单动态规划==记忆搜索法==>枚举所有可可能性
    public int moneyTarget3(int[] arr, int target){
        if (arr == null || arr.length == 0 || target < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][target + 1];
        //base case
        dp[arr.length][0] = 1;

        for (int i = 0; i < arr.length + 1; i++) {
            dp[i][0] = 1;
        }

        //dp[i][rest]简单动态规划，有几个遍历就有几个循环，如果枚举所有值就要在加上一个循环
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int rest = 1; rest <= target; rest++) {//这个地方要遍历所有的可能，没有简单搜索法好用
                int ways = 0;
                for (int zhang = 0; arr[i] * zhang <= rest; zhang++) {
                    ways += dp[i + 1][rest - zhang * arr[i]];
                    if (rest - zhang * arr[i] == 0) { //细节优化，如果已经等于0表面已经凑齐，后面都应该取0就可以了，无需再遍历，返回当前结果就行了，要加上dp[i][0]的basecase
                        break;
                    }
                }
                dp[i][rest] = ways;
            }

        }
        return dp[0][target];
    }

    //经典动态规划==>对所有枚举的方式做总结，只使用部分枚举数据
    public int moneyTarget4(int[] arr, int target){
        if (arr == null || arr.length == 0 || target < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][target + 1];
        //base case
        dp[arr.length][0] = 1;
/*        for (int i = 0; i < arr.length + 1; i++) {
            dp[i][0] = 1;
        }*/

        //dp[i][rest]简单动态规划，有几个遍历就有几个循环，如果枚举所有值就要在加上一个循环
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int rest = 0; rest <= target; rest++) {//这个地方要遍历所有的可能，没有简单搜索法好用
                dp[i][rest] += dp[i + 1][rest];
                if (rest >= arr[i]) {
                    dp[i][rest] += dp[i][rest - arr[i]];
                }
                //  dp[i][rest] = dp[i + 1][rest]+dp[i][rest - arr[i]] 关键的这个地方的规律
            }
        }
        return dp[0][target];
    }


    //暴力递归
    public int walk(int n, int m, int k, int p){
        //无效条件，比较多暂时不写了
        if (n < 2 || k < 1 || m < 1 || m > n || p < 1 || p > n) {
            return 0;
        }
        return walkProcess(n, m, k, p);
    }

    //n表示范围 m开始位置 k移动步数 p结束位置
    private int walkProcess(int n, int m, int k, int p){
        if (k == 0) {
            return m == p ? 1 : 0;
        }
        if (m == 1) {
            return walkProcess(n, m + 1, k - 1, p);
        }
        if (m == n) {
            return walkProcess(n, m - 1, k - 1, p);
        }
        return walkProcess(n, m - 1, k - 1, p) + walkProcess(n, m + 1, k - 1, p);//只有m和k的变量在递归中变化
    }

    //暴力递归加上缓存，缓存计算过的计算过程
    public int walkCache(int n, int m, int k, int p){
        //无效条件，比较多暂时不写了
        if (n < 2 || k < 1 || m < 1 || m > n || p < 1 || p > n) {
            return 0;
        }
        int[][] dp = new int[m + 1][k + 1];//表示在m位置上移动k步的结果，默认为-1，未计算到，计算到了表面有值
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = -1;
            }
        }
        return walkCacheProcess(n, m, k, p, dp);
    }

    //n表示范围 m开始位置 k移动步数 p结束位置
    private int walkCacheProcess(int n, int m, int k, int p, int[][] dp){
        if (dp[m][k] != -1) {//说明计算过了
            return dp[m][k];
        }
        //计算值要缓存
        if (k == 0) {
            dp[m][k] = m == p ? 1 : 0;
            return dp[m][k];
        }
        if (m == 1) {
            dp[m][k] = walkProcess(n, m + 1, k - 1, p);
            return dp[m][k];

        }
        if (m == n) {
            dp[m][k] = walkProcess(n, m - 1, k - 1, p);
            return dp[m][k];

        }
        dp[m][k] = walkProcess(n, m - 1, k - 1, p) + walkProcess(n, m + 1, k - 1, p);//只有m和k的变量在递归中变化
        return dp[m][k];

    }

    //动态规划标准写法
    private int walkDynamicProgramming(int n, int m, int k, int p){
        if (n < 2 || k < 1 || m < 1 || m > n || p < 1 || p > n) {
            return 0;
        }
        int[][] dp = new int[k + 1][n + 1];//在 m位置上 k的解法
        dp[0][p] = 1;//在p点没有步数时为一次==>其他情况 dp[k][0]为默认0

        //二维数组循环先开始那个 n表示起点位置 k表示移动步数
        //下面的循环表示 在i位置上，一直移动 这不是有问题吗
/*        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {//k在循环里面 每次移动一步
                if (i == 1) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else if (i == n) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1];
                }
            }
        }*/
        //应该是剩余K步，在不同位置上的解法
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                if (j == 1) {
                    dp[i][j] = dp[i - 1][j + 1];
                } else if (j == n) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[k][m];
    }


}
